package com.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 427. 建立四叉树
 * 递归
 * 2022-04-29 每日一题
 *
 * @author fy
 * @date 2022/4/29 9:07
 */
public class Solution427 {

    // Definition for a QuadTree node.
    static class Node {
        public boolean val;
        public boolean isLeaf;
        public Node topLeft;
        public Node topRight;
        public Node bottomLeft;
        public Node bottomRight;


        public Node() {
            this.val = false;
            this.isLeaf = false;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = null;
            this.topRight = null;
            this.bottomLeft = null;
            this.bottomRight = null;
        }

        public Node(boolean val, boolean isLeaf, Node topLeft, Node topRight, Node bottomLeft, Node bottomRight) {
            this.val = val;
            this.isLeaf = isLeaf;
            this.topLeft = topLeft;
            this.topRight = topRight;
            this.bottomLeft = bottomLeft;
            this.bottomRight = bottomRight;
        }
    }

    /**
     * 我们可以按以下步骤为二维区域构建四叉树：
     *
     * 1. 如果当前网格的值相同（即，全为 0 或者全为 1），将 isLeaf 设为 True ，
     *      将 val 设为网格相应的值，并将四个子节点都设为 Null 然后停止。
     * 2. 如果当前网格的值不同，将 isLeaf 设为 False， 将 val 设为任意值，
     *      然后如下图所示，将当前网格划分为四个子网格。
     * 3. 使用适当的子网格递归每个子节点。
     *
     * @param grid
     * @return
     */
    public Node construct(int[][] grid) {
        if (isSameVal(grid)) {
            return new Node(grid[0][0] == 1, true);
        } else {
            List<int[][]> list = split(grid);
            Node node = new Node(grid[0][0] == 1, false);
            node.topLeft = construct(list.get(0));
            node.topRight = construct(list.get(1));
            node.bottomLeft = construct(list.get(2));
            node.bottomRight = construct(list.get(3));
            return node;
        }
    }

    private List<int[][]> split(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        if (m == 1 || n == 1) {
            throw new RuntimeException("wrong grid");
        }
        int[][] topLeft = new int[m / 2][n / 2];
        int[][] topRight = new int[m / 2][n / 2];
        int[][] bottomLeft = new int[m / 2][n / 2];
        int[][] bottomRight = new int[m / 2][n / 2];

        int k = 0;
        int l = 0;
        for (int i = 0; i < m / 2; i++) {
            for (int j = 0; j < n / 2; j++) {
                topLeft[k][l] = grid[i][j];
                l++;
            }
            k++;
            l = 0;
        }

        k = 0;
        l = 0;
        for (int i = 0; i < m / 2; i++) {
            for (int j = n / 2; j < n; j++) {
                topRight[k][l] = grid[i][j];
                l++;
            }
            k++;
            l = 0;
        }

        k = 0;
        l = 0;
        for (int i = m / 2; i < m; i++) {
            for (int j = 0; j < n / 2; j++) {
                bottomLeft[k][l] = grid[i][j];
                l++;
            }
            k++;
            l = 0;
        }

        k = 0;
        l = 0;
        for (int i = m / 2; i < m; i++) {
            for (int j = n / 2; j < n; j++) {
                bottomRight[k][l] = grid[i][j];
                l++;
            }
            k++;
            l = 0;
        }

        List<int[][]> list = new ArrayList<>();
        list.add(topLeft);
        list.add(topRight);
        list.add(bottomLeft);
        list.add(bottomRight);

        return list;
    }

    private boolean isSameVal(int[][] grid) {
        if (grid == null || grid.length == 0) {
            return true;
        }
        int val = grid[0][0];
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (val != grid[i][j]) {
                    return false;
                }
            }
        }
        return true;
    }


    public static void main(String[] args) {
        int[][] grid = new int[][]{{1, 1, 0, 0}, {1, 1, 0, 0}, {0, 0, 1, 1}, {0, 0, 1, 1}};
        Node root = new Solution427().construct(grid);
        System.out.println(root);
    }

}
